Practice | GeeksforGeeks | A computer science portal for geeks
▲
LIVE   BATCHES

This track of the course covers the topic "Stack".

In details, this track will cover:

  • Basics: Introduction to the stack data structure. We'll look at insertion and deletion order in a stack.
  • Operations: Various operations like push, pop, top, empty.
  • Implementation: How to implement Stack in CPP and Java using arrays and linked lists.
  • Expressions: We'll study infix, postfix, prefix expressions and conversion from one to other. We'll take a look at the evaluation of these expressions.

Objective: The objective of this track is to familiarize the learners with Stack.

Track Content:

  • 1 Video Lecture on Stack.
  • Theoretical Articles.
  • Progrraming practice problems.
  • 10 Quiz questions for practice.

Assessment: All Tracks in every week are associated with weekly contests.

We have combined Classroom and Theory tab and created a new Learn tab for easy access. You can access Classroom and Theory from the left panel.
Classroom Theory

  Stack Data Structure 


Stack Data Structure
Codes:

  Array Implementation of Stack in C++ 


Array Implementation of Stack in C++
Codes:

  Array Implementation of Stack in Java 


Array Implementation of Stack in Java
Codes:

  Linked List Implementation of Stack in C++ 


Linked List Implementation of Stack in C++
Code:

  Linked List Implementation of Stack in Java 


Linked List Implementation of Stack in Java
Code:

  Stack Applications 


This video discusses the various applications of Stack.

  Stack in C++ STL 


This video discusses the implementation of Stack in C++.
Code:

  Stack in Java Collections 


In this video we'll talk about stack in java collections

Code:

  Balanced Parenthesis 


This video discusses the below problem:
Given a string of parenthesis ({, }, (, ), [ and ]), we need to check if this string is balanced or not.
Code:

  Two stacks in an array 


This video discusses the problem of implementation of Two stacks in a single array.
Codes:

  K Stacks in an array 


This video discusses the problem of implementation of K Stacks in an array
Codes:

  Stock span problem 


This video discusses the problem of Stock span problem along with few variations.
Codes:

  Previous Greater Element 


This video discusses the below problem:
Given an array of distinct integers, find the closest (positive wise) greater on left of every element. If there is no greater element on l;eft, then print -1
Codes:

  Next Greater Element 


This video discusses the below problem:
Given an array of distinct integers, find the NextGreater(position-wise closest and on the right side) of every array elements.
Codes:

  Largest Rectangular Area in a Histogram (Part 1) 


This video discusses the first part of the problem of calculating the Largest Rectangular Area in a Histogram.
Codes:

  Largest Rectangular Area in a Histogram (Part 2) 


This video discusses the second part of the problem of calculating the Largest Rectangular Area in a Histogram.
Codes:

  Largest Rectangle with all 1's 


Largest Rectangle with all 1's
Codes:

  Stack with getMin() in O(1) 


Design a stack that supports normal stack operatiosn in O(1) and also supprots getMin() in O(1)
Codes:

  Design a Stack with getMin() in O(1) Space 


Design A Stack With Get Min() in O(1) Space
Codes:

  Infix, Prefix and Postfix Introduction 


Infix, prefix and Postfix are three different ways to write mathematical expressions. This video introduces these three and talks about their advantages/distadvantages.

  Infix to Postfix (Simple Solution) 


This video talks about simple method for Infix to Postfix conversion.

  Infix to Postfix (Efficient Solution) 


This video talks about infix to postfix conversion using stack.

  Evaluation of Postfix 


This video talks about a simple, efficient and stack based solution for evaluation of postfix.

  Infix to Prefix (Simple Solution) 


This video talks about simple method for Infix to Prefix Conversion.

  Infix to Prefix (Efficient Solution) 


This video talks about stack based efficient solution for Infix to Prefx conversion.

  Evaluation of Prefix 


This method talks about simple, efficient and stack based solution for evaluation of prefix.

  Introduction to Stacks 

The Stack is a linear data structure, which follows a particular order in which the operations are performed. The order may be LIFO(Last In First Out) or FILO(First In Last Out).
  • The LIFO order says that the element which is inserted at the last in the Stack will be the first one to be removed. In LIFO order, the insertion takes place at the rear end of the stack and deletion occurs at the front of the stack.
  • The FILO order says that the element which is inserted at the first in the Stack will be the last one to be removed. In FILO order, the insertion takes place at the rear end of the stack and deletion occurs at the front of the stack.

Mainly, the following three basic operations are performed in the stack:
  • Push: Adds an item in the stack. If the stack is full, then it is said to be an Overflow condition.
  • Pop: Removes an item from the stack. The items are popped in the reversed order in which they were pushed. If the stack is empty, then it is said to be an Underflow condition.
  • Peek or Top: Returns the top element of the stack.

  • isEmpty: Returns true if the stack is empty, else false.


stack

How to understand a stack practically?

There are many real-life examples of a stack. Consider the simple example of plates stacked over one another in a canteen. The plate that is at the top is the first one to be removed, i.e. the plate that has been placed at the bottommost position remains in the stack for the longest period of time. So, it can be simply seen to follow LIFO/FILO order.

Time Complexities of operations on stack: The operations push(), pop(), isEmpty() and peek() all take O(1) time. We do not run any loop in any of these operations.


Implementation: There are two ways to implement a stack.
  • Using array
  • Using linked list

Implementing Stack using Arrays

XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
Output : 
10 pushed into stack

20 pushed into stack

30 pushed into stack

30 popped from stack

Pros: Easy to implement. Memory is saved as pointers are not involved.
Cons: It is not dynamic. It doesn’t grow or shrink depending on needs at runtime.


Implementing Stack using Linked List

XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
Output:
10 pushed to stack

20 pushed to stack

30 pushed to stack

30 popped from stack

Top element is 20

Pros: The linked list implementation of stack can either grow or shrink according to the needs at runtime.
Cons: Requires extra memory due to involvement of pointers.


Applications of stack:
  • Stacks can be used to check for the balancing of paranthesis in an expression.
  • Infix to Postfix/Prefix conversion.
  • Redo-undo features at many places such as editors, photoshop, etc.
  • Forward and backward feature in web browsers.
    • And Many More...

  Implementing Stacks in C++ and Java using built-in Classes 

Stack in C++ STL

The C++ STL offers a built-in class named stack for implementing the stack data structure easily and efficiently. This class provides almost all functions needed to perform the standard stack operations like push(), pop(), peek(), remove() etc..

Syntax:
stack< data_type > stack_name;

Here,
data_type: This defines the type of data to be 
           stored in the stack.
stack_name: This specifies the name of the stack.

Some Basic functions of Stack class in C++:
  • empty() – Returns whether the stack is empty.
  • size() – Returns the size of the stack.
  • top() – Returns a reference to the topmost element of the stack.
  • push(g) – Adds the element ‘g’ at the top of the stack.
  • pop() – Deletes the topmost element of the stack.
    • All of the above functions work in O(1) time complexity.

Implementation:
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
Output:
The stack is :     1    5    20    30    10

s.size() : 5
s.top() : 1
s.pop() :     5    20    30    10

Stack class in Java

Java Collection framework provides a Stack class which models and implements the Stack data structure. The class is based on the basic principle of last-in-first-out. In addition to the basic push and pop operations, the class provides three more functions of empty, search and peek. The class can also be said to extend Vector and treats the class as a stack with the five mentioned functions. The class can also be referred to as the subclass of Vector.

This diagram shows the hierarchy of Stack class:

The class supports one default constructor Stack() which is used to create an empty stack.

Below program shows a few basic operations provided by the Stack class:
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Output: 
Pop :
4
3
2
1
0
Element on stack top : 4
Element is found at position 3
Element not found

Methods in Stack class:
  1. Object push(Object element) : Pushes an element on the top of the stack.
  2. Object pop() : Removes and returns the top element of the stack. An 'EmptyStackException' exception is thrown if we call pop() when the invoking stack is empty.
  3. Object peek() : Returns the element on the top of the stack, but does not remove it.
  4. boolean empty() : It returns true if nothing is on the top of the stack. Else, returns false.
  5. int search(Object element) : It determines whether an object exists in the stack. If the element is found, it returns the position of the element from the top of the stack. Else, it returns -1.

  Infix to Postfix conversion using Stack 

Infix expression: The expression of the form a op b. When an operator is in-between every pair of operands.

Postfix expression: The expression of the form a b op. When an operator is followed for every pair of operands.

Why postfix representation of the expression? The compiler scans the expression either from left to right or from right to left.

Consider the below expression: 
a op1 b op2 c op3 d

If op1 = +, op2 = *, op3 = +
The compiler first scans the expression to evaluate the expression b * c, then again scan the expression to add a to it. The result is then added to d after another scan.

The repeated scanning makes it very in-efficient. It is better to convert the expression to postfix(or prefix) form before evaluation.

The corresponding expression in postfix form is: abc*+d+. The postfix expressions can be evaluated easily using a stack. We will cover postfix expression evaluation in a separate post.

Algorithm to Convert an Infix expression to Postfix:
  1. Scan the infix expression from left to right.
  2. If the scanned character is an operand, output it.
  3. Else,
    • If the precedence of the scanned operator is greater than the precedence of the operator in the stack(or the stack is empty or the stack contains a '(' ), push it.
    • Else, Pop all the operators from the stack which are greater than or equal to in precedence than that of the scanned operator. After doing that Push the scanned operator to the stack. (If you encounter parenthesis while popping then stop there and push the scanned operator in the stack.)
  4. If the scanned character is an ‘(‘, push it to the stack.
  5. If the scanned character is an ‘)’, pop the stack and and output it until a ‘(‘ is encountered, and discard both the parenthesis.
  6. Repeat steps 2-6 until infix expression is scanned.
  7. Print the output.
  8. Pop and output from the stack until it is not empty.


Below is the implementation of the above algorithm:
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
Output: 
abcd^e-fgh*+^*+i-

  Evaluating Postfix expressions using Stack 

The Postfix notation is used to represent algebraic expressions. The expressions written in postfix form are evaluated faster compared to infix notation as parenthesis are not required in postfix. We have already discussed the conversion of infix to postfix expressions. In this post, the next step after that, that is evaluating a postfix expression is discussed.


Following is the algorithm for evaluation of postfix expressions:
  1. Create a stack to store operands (or values).
  2. Scan the given expression and do following for every scanned element.
    • If the element is a number, push it into the stack.
    • If the element is an operator, pop operands for the operator from the stack. Evaluate the operator and push the result back to the stack.
  3. When the expression is ended, the number in the stack is the final answer.

Example: Let the given expression be "2 3 1 * + 9 -". We will first scan all elements one by one.
  1. Scan '2', it's a number, so push it to stack. Stack contains '2'
  2. Scan '3', again a number, push it to stack, stack now contains '2 3' (from bottom to top)
  3. Scan '1', again a number, push it to stack, stack now contains '2 3 1'
  4. Scan '*', it's an operator, pop two operands from the stack, apply the * operator on operands, we get 3*1 which results in 3. We push the result '3' to stack. Stack now becomes '2 3'.
  5. Scan '+', it's an operator, pop two operands from the stack, apply the + operator on operands, we get 3 + 2 which results in 5. We push the result '5' to stack. Stack now becomes '5'.
  6. Scan '9', it's a number, we push it to the stack. Stack now becomes '5 9'.
  7. Scan '-', it's an operator, pop two operands from the stack, apply the - operator on operands, we get 5 - 9 which results in -4. We push the result '-4' to stack. Stack now becomes '-4'.
  8. There are no more elements to scan, we return the top element from the stack (which is the only element left in the stack).

Below is the implementation of the above algorithm:
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
Output: 
postfix evaluation: -4

The time complexity of evaluation algorithm is O(n) where n is number of characters in input expression.
There are following limitations of the above implementation:
  1. It supports only 4 binary operators '+', '*', '-' and '/'. It can be extended for more operators by adding more switch cases.
  2. The allowed operands are only single-digit operands. The program can be extended for multiple digits by adding a separator like space between all elements (operators and operands) of the given expression.

Below given is the extended program which allows operands having multiple digits.
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
Output : 
757

  Implementing two Stacks using One Array 

The task is to create a data structure twoStacks that represents two stacks. Implementation of twoStacks should use only one array, i.e., both stacks should use the same array for storing elements. Following functions must be supported by twoStacks.
  • push1(int x) --> pushes x to first stack.
  • push2(int x) --> pushes x to second stack.
  • pop1() --> pops an element from the first stack and return the popped element.
  • pop2() --> pops an element from the second stack and return the popped element.

Note: Implementation of twoStack should be space efficient.


Method 1 (Divide the space in two halves): A simple way to implement two stacks is to divide the array into two halves and assign the half space to the first stack and the other half to the second stack, i.e., use arr[0] to arr[n/2] for stack1, and arr[(n/2) + 1] to arr[n-1] for stack2 where arr[] is the array to be used to implement two stacks and size of array be n.

The problem with this method is an inefficient use of array space. A stack push operation may result in stack overflow even if there is space available in arr[]. For example, say the array size is 6 and we push 3 elements to stack1 and do not push anything to the second stack2. When we push the 4th element to stack1, there will be overflow even if we have space for 3 more elements in the array.

Method 2 (A space-efficient implementation): This method efficiently utilizes the available space. It doesn't cause an overflow if there is space available in arr[]. The idea is to start two stacks from two extreme corners of arr[]. The first stack, stack1 starts from the leftmost element, the first element in stack1 is pushed at index 0. The second stack, stack2 starts from the rightmost corner, the first element in stack2 is pushed at index (n-1). Both stacks grow (or shrink) in opposite direction. To check for overflow, all we need to check is for space between top elements of both stacks.

Below the space-efficient implementation(Method 2) of the above task:
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
Output: 
Popped element from stack1 is 11
Popped element from stack2 is 40

The time complexity of all of the four push and pop operations of both stacks is O(1).

  Sample Problems on Stack 

Problem #1 : Print Reverse of linked List using Stack.

Description - We are given a linked list. We have to print the reverse of the linked list using Stack.
[1 2 3 4 5]
[5 4 3 2 1]
Solution - We will traverse the linked list and push all the nodes of the linked list to the stack. Since stack have property of Last In, First Out, List is automatically reversed when we will pop the stack elements one by one.
Pseudo Code 
void printreverse(Node *head)
{
    stack < Node* > s
    current = head
    while(current != NULL)
    {
        s.push(current)
        current = current->next
    }
    while( ! s.empty())
    {
        node = s.top()
        print(node->data)
        s.pop()
    }
}
Time Complexity : O(n)
Auxiliary Space : O(n)

Problem #2 : Check for balanced parentheses in an expression

Description - Given an expression string exp , we have to check whether the pairs and the orders of { “ , ” } , ( “ , ” ) and [ “ , ” ] are correct in exp. For example -
Input : [ ( ) ] { } { [ ( ) ( ) ] ( ) }
Output : true
Input : [ ( ] )
Output : false
Solution : Follow the streps below -
  1. Declare a character stack S.
  2. Now traverse the expression string exp.
    • If the current character is a starting bracket ‘(‘ or ‘{‘ or ‘[‘ then push it to stack.
    • If the current character is a closing bracket ‘)’ or ‘}’ or ‘]’ then pop from stack and if the popped character is the matching starting bracket then fine else parenthesis are not balanced.
  3. After complete traversal, if there is some starting bracket left in stack then “not balanced”.
Pseudo Code 
// function to check if paranthesis are balanced 
bool areParanthesisBalanced(string expr) 
{
    stack < char > s 

    for i=0 to expr.size() {

        if (expr[i]=='('||expr[i]=='['||expr[i]=='{') {
            s.push(expr[i])
            continue 
        }
        // stack can not be empty for closing bracket
        if s.empty() 
            return false
  
        switch (expr[i]) {
            case ')':  {
                x = s.top()
                s.pop()
                if (x=='{' || x=='[') 
                    return false
                break 
            }
            case '}':  {
                x = s.top(); 
                s.pop(); 
                if (x=='(' || x=='[') 
                    return false 
                break
            }
            case ']':  {
                x = s.top(); 
                s.pop(); 
                if (x =='(' || x == '{') 
                    return false
                break
            }
        }
    }
    // Check Empty Stack 
    return (s.empty())
}
Time Complexity : O(n)
Auxiliary Space : O(n)

Problem #3 : Next Greater Element

Description : Given an array, print the Next Greater Element (NGE) for every element. The Next greater Element for an element x is the first greater element on the right side of x in array. Elements for which no greater element exist, consider next greater element as -1.
Input : [13, 7, 6, 12]
       Output
 Element       NGE
   13   -->     -1
   7    -->     12
   6    -->     12
   12   -->     -1
Solution : Follow the below steps -
  1. Push the first element to stack.
  2. Pick rest of the elements one by one and follow the following steps in the loop.
    1. Mark the current element as next.
    2. If the stack is not empty, compare top element of the stack with next.
    3. If next is greater than the top element, Pop element from the stack. next is the next greater element for the popped element.
    4. Keep popping from the stack while the popped element is smaller than next. next becomes the next greater element for all such popped elements
    5. Finally, push the next in the stack.
  3. After the loop in step 2 is over, pop all the elements from stack and print -1 as the next element for them.
Pseudo Code 
// Next greater Element
void printNGE(arr, n) 
{
    stack < int > s
    s.push(arr[0])
    for i=0 to n-1 {
        if (s.empty()) {
            s.push(arr[i])
            continue
        }
        while (s.empty() == false && s.top() < arr[i]) {
            print(s.top() + "-->" + arr[i])         
            s.pop() 
        }
        s.push(arr[i])
        while (s.empty() == false) {
            print(s.top() + "-->" + -1) 
            s.pop()
        }
    }
}
Time Complexity : O(n)
Auxiliary Space : O(n)



Implement stack using array

Asked In: FactSet Goldman Sachs Kritikal Solutions Qualcomm Visa

Submissions: 42347   Accuracy:

50%

  Difficulty: Basic   Marks: 1
Implement Stack using Linked List

Asked In: Codenation FactSet Microsoft Samsung SAP Labs

Submissions: 43519   Accuracy:

49.96%

  Difficulty: Basic   Marks: 1
Operations on Stack
Submissions: 5569   Accuracy:

66.49%

  Difficulty: Basic   Marks: 1
Removing consecutive duplicates
Submissions: 4609   Accuracy:

78.06%

  Difficulty: Easy   Marks: 2
Removing consecutive duplicates - 2
Submissions: 5303   Accuracy:

64.25%

  Difficulty: Easy   Marks: 2
Parenthesis Checker

Asked In: Adobe Amazon Flipkart Oracle OYO Rooms Snapdeal Walmart Yatra.com Microsoft

Submissions: 31893   Accuracy:

49.12%

  Difficulty: Easy   Marks: 2
Implement two stacks in an array

Asked In: 24*7 Innovation Labs Microsoft Samsung Snapdeal

Submissions: 40554   Accuracy:

49.76%

  Difficulty: Easy   Marks: 2
Get min at pop
Submissions: 17118   Accuracy:

52.66%

  Difficulty: Easy   Marks: 2
Delete middle element of a stack
Submissions: 21133   Accuracy:

50.06%

  Difficulty: Easy   Marks: 2
Infix to Postfix

Asked In: Paytm VMWare Microsoft

Submissions: 3677   Accuracy:

37.51%

  Difficulty: Easy   Marks: 2
Evaluation of Postfix Expression
Submissions: 10607   Accuracy:

53.38%

  Difficulty: Easy   Marks: 2
Stock span problem

Asked In: Accolite Samsung Amazon Microsoft

Submissions: 14678   Accuracy:

49.89%

  Difficulty: Medium   Marks: 4
Next Greater Element

Asked In: Flipkart Amazon Microsoft

Submissions: 21855   Accuracy:

48.92%

  Difficulty: Medium   Marks: 4
Maximum Rectangular Area in a Histogram

Asked In: Microsoft

Submissions: 12588   Accuracy:

47.42%

  Difficulty: Medium   Marks: 4
The Celebrity Problem

Asked In: Amazon Fab.com Flipkart Google Microsoft One97 United Health Group Zoho

Submissions: 56105   Accuracy:

39.46%

  Difficulty: Medium   Marks: 4
Maximum of minimum for every window size

Asked In: Amazon Microsoft

Submissions: 4981   Accuracy:

39.42%

  Difficulty: Hard   Marks: 8
Question 1 [1 Marks]
Consider n elements that are equally distributed in k stacks. In each stack, elements of it are arranged in ascending order (min is at the top in each of the stack and then increasing downwards).

Given a queue of size n in which we have to put all n elements in increasing order. What will be the time complexity of the best known algorithm?
A
O(n logk)
B
O(nk)
C
O(n<sup>2</sup>)
D
O(k<sup>2</sup>)
Explanation

If you are facing any issue on this page. Please let us know.